//给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,2,3,3,4,4,8,8]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: nums =  [3,3,7,7,10,11,11]
//输出: 10
// 
//
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 105 
// 0 <= nums[i] <= 105 
// 
//
// 
//
// 进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？ 
// Related Topics 数组 二分查找 
// 👍 285 👎 0

package com.cute.leetcode.editor.cn;
public class SingleElementInASortedArray {
    public static void main(String[] args) {
        Solution solution = new SingleElementInASortedArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 时间复杂度为logn 空间复杂度为1
         * 利用排序数组的性质以及只有一个单一元素的条件
         * 首先原始数组元素的个数肯定是奇数的，l = 0  r = len-1
         * mid取中间值之后进行判断，可以判断根据mid的奇偶性来判断目标元素在哪边
         * 目标元素所在的部分长度一定是奇数
         *  1.如果mid是偶数，且mid下一位和mid处值相等，那么一定是向右搜索了
         *  2.如果mid是奇数，且mid的前一位和mid处相等，仍然要向右搜索
         *  3.不然就要向左进行搜索了
         * 因为正常成对出现的元素，一定是在偶数位开始，奇数位结束的
         */
        public int singleNonDuplicate(int[] nums) {
            int left = 0;
            int right = nums.length-1;
            int mid;
            while (left < right){//这里绝对不能加等号，不然就死循环了
                mid = left + (right - left)/2;//取中间坐标
                //如果mid是偶数，且mid下一位和mid处值相等，那么一定是向右搜索了
                if ((mid & 1) == 0 && nums[mid] == nums[mid+1]) left = mid + 2;
                //如果mid是奇数，且mid的前一位和mid处相等，仍然要向右搜索
                else if ((mid & 1) == 1 && nums[mid] == nums[mid-1]) left = mid +1;
                else right = mid;//此时应该向左搜索才行
            }
            return nums[left];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}